#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;cin>>n>>m;
	cin.ignore();
	string num;
	vector<int> nums;
	int t=n;
	while(n--){
		int t;
		cin>>t;
		nums.push_back(t);
	}
	cin.ignore();
	n=t;
	int idx=0;
	while(t--){
		if(t==n){
			num+=to_string(nums[idx++]);
		}else
		num+=" "+to_string(nums[idx++]);
	}
	while(m--){
		int yy;cin>>yy;
		if(yy==1){
			string s1,s2;
			getline(cin,s1);
			getline(cin,s2);
			auto t=num.find(s1);
			if(t!=string::npos){
				int len=s1.length();
				string s11,s22;
				s11=num.substr(0,t);
				s22=num.substr(t+len);
				num.clear();
				num=s11+s2+s22;
				nums.clear();
				int ll=nums.size(),v=0;;
				for(int i=0;i<ll;i++){
					if(isdigit(num[i])){
						v=v*10+(int)(num[i]-'0');
					}if(!isdigit(num[i])||i==ll-1){
						nums.push_back(v);
						v=0;
					}
				}
			}
		}
		if(yy==2){
			int id=0;
			vector<int> n;
			for(int j=0;j<nums.size()-1;j++){
				if((nums[j]+nums[j+1])%2==0){
					n.push_back(nums[id]);
					n.push_back((nums[id]+nums[id+1])/2);
					n.push_back(nums[id]);
					id+=2;
				}else{
					n.push_back(nums[id++]);
				}
			}
			nums=n;
			num.clear();
			auto tt=nums.size();
			int nn=(int)tt;
		idx=0;
		while(tt--){
			if(tt==nn){
				num+=to_string(nums[idx++]);
			}else
			num+=" "+to_string(nums[idx++]);
		}
			
			
		}
		if(yy==3){
			int l,r;cin>>l>>r;
			for(int i=0;i<(r-l)/2;i++){
				int t=nums[r+i];
				nums[r+i]=nums[l-i];
				nums[l-i]=t;
			}
			num.clear();
			auto tt=nums.size();
			int nn=(int)tt;
	idx=0;
	while(tt--){
		if(tt==nn){
			num+=to_string(nums[idx++]);
		}else
		num+=" "+to_string(nums[idx++]);
	}
			
			
		}
	}
	cout<<num;
	return 0;
}